/* 
 * Given an array S of n integers, find three integers in S such that the sum is closest to a given number
 * Return the sum of three integers.
 * You may assume that each input would have exactly one solution
 * For example, S = {-1 2 1 4}, target = 1. the sum that is closet  to the target is 2. (-1+2+1=2)
 */

#include "../../func.h"

int threeSumClosest(vector<int> &nums, int target)
{
    int ret = 0;
    int min_gap = INT_MAX;

    sort(nums.begin(), nums.end());

    for (auto a = nums.begin(); a != prev(nums.end(), 2); ++a)
    {
        auto b = next(a);
        auto c = prev(nums.end());

        while (b < c)
        {
            const int sum = *a + *b + *c;
            const int gap = abs(sum - target);
            if (gap < min_gap)
            {
                ret = sum;
                min_gap = gap;
            }

            if (sum < target)
                ++b;
            else
                --c;
        }
    }
}